/**
 * Project of Vehicle Routing Problem with Time Windows implements 
 * some of well-known algorithms for solving VRPTW and presents new 
 * one.
 *
 * @author Michal Drobny  
 */
package heuristic;

import java.util.Set;

import logic.destination.Destination;
import logic.evaluator.Evaluator;
import logic.restriction.enumeration.IterationType;
import logic.restrictionAdapter.RestrictionAdapter;
import logic.route.Cycle;

/**
 * Represents the Cheapest inserting method for solving VRP problem.
 * 
 * @author Michal Drobny
 * @date 7.11.2014
 */
public class CheapestInserting extends AbstractInsertingMethod {

	@Override
	protected Cycle addNextDestination(Cycle cycle,
			Set<Destination> unusedDestinations, Evaluator evaluator,
			RestrictionAdapter restrictionAdapter) {
		
		Double bestValue = Double.MAX_VALUE;
		Destination bestDestination = null;
		Cycle bestCycle = null;
		Cycle testCycle = new Cycle(cycle.getDestinations());
		
		for (Destination unusedDestination : unusedDestinations) {
			for (int i = 0; i < cycle.getDestinations().size(); ++i) {
				Destination cycleDestination = cycle.getDestinations().get(i);
				Destination cycleNextDestination = cycle.getDestinations().get((i + 1) % cycle.getDestinations().size());
				testCycle.addAfter(unusedDestination, cycleDestination);
				Double currentValue = evaluator.evaluate(cycleDestination, unusedDestination)
						+ evaluator.evaluate(unusedDestination, cycleNextDestination);
				
				if (restrictionAdapter.canIterate(IterationType.CYCLE, testCycle) && currentValue < bestValue) {
					bestValue = evaluator.evaluate(cycleDestination, unusedDestination);
					bestDestination = unusedDestination;
					bestCycle = new Cycle(testCycle.getDestinations());
				}
				
				testCycle.remove(unusedDestination);
			}
		}
		
		if (bestCycle != null) {
			unusedDestinations.remove(bestDestination);
			return bestCycle;
		} else
			return null;
	}

}